//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//  This file is part of the buola project (https://code.google.com/p/buola/).  //
//                                                                              //
//  Copyright(c) 2007-2011 Xavi Gratal                                          //
//  gratal AT gmail DOT com                                                     //
//                                                                              //
//  Buola is free software: you can redistribute it and/or modify               //
//  it under the terms of the GNU General Public License as published by        //
//  the Free Software Foundation, either version 3 of the License, or           //
//  (at your option) any later version.                                         //
//                                                                              //
//  Buola is distributed in the hope that it will be useful,                    //
//  but WITHOUT ANY WARRANTY; without even the implied warranty of              //
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               //
//  GNU General Public License for more details.                                //
//                                                                              //
//  You should have received a copy of the GNU General Public License           //
//  along with buola.  If not, see <http://www.gnu.org/licenses/>.              //
//                                                                              //
//////////////////////////////////////////////////////////////////////////////////

#ifndef _BUOLA_ALGORITHM_COMPARISON_H_
#define _BUOLA_ALGORITHM_COMPARISON_H_

#include <buola/functors/predicates/binary.h>
#include <buola/functors/predicates/case.h>
#include <buola/iterator/range.h>

namespace buola {

///\addtogroup algorithm
///@{

///\name Comparison
//@{

///\cond
namespace detail
{
    //overload for ranges with a "fast size"
    template<typename t1,typename t2,typename tPredicate>
    bool equals(const t1 &p1,const t2 &p2,tPredicate pComp,std::true_type)
    {
        return range_size(p1)==range_size(p2)&&std::equal(range_begin(p1),range_end(p1),range_begin(p2),pComp);
    }

    //overload for the rest of ranges
    template<typename t1,typename t2,typename tPredicate>
    bool equals(const t1 &p1,const t2 &p2,tPredicate pComp,std::false_type)
    {
        auto l1I=range_begin(p1);
        auto l2I=range_begin(p2);

        auto l1E=range_end(p1);
        auto l2E=range_end(p2);

        while(l1I!=l1E)
        {
            if(l2I==l2E) return false;
            if(!pComp(*l1I,*l2I)) return false;

            ++l1I;
            ++l2I;
        }

        return l2I==l2E;
    }

    //overload for ranges with a "fast size"
    template<typename tInput,typename tTest,typename tPredicate>
    bool starts_with(const tInput &pInput,const tTest &pTest,tPredicate pComp,std::true_type)
    {
        return range_size(pTest)<=range_size(pInput)&&std::equal(range_begin(pTest),range_end(pTest),
                                                                 range_begin(pInput),pComp);
    }

    //overload for the rest of ranges
    template<typename tInput,typename tTest,typename tPredicate>
    bool starts_with(const tInput &pInput,const tTest &pTest,tPredicate pComp,std::false_type)
    {
        auto lInputI=range_begin(pInput);
        auto lTestI=range_begin(pTest);

        auto lInputE=range_end(pInput);
        auto lTestE=range_end(pTest);

        while(lTestI!=lTestE)
        {
            if(lInputI==lInputE) return false;
            if(!pComp(*lInputI,*lTestI)) return false;

            ++lTestI;
            ++lInputI;
        }

        return true;
    }
}
///\endcond
    
///check if all the elements in two ranges are equal

///\param p1 the first range
///\param p2 the second range
///\param pComp the function to use to check for element equality
///
///\return `true` if all elements in the two ranges are equal
///
///If it is possible to obtain the size of the range in a fast way (random-access iterator ranges and containers
///with a size() function) then the size will be checked first and std::equal will be used.
template<typename t1,typename t2,typename tPredicate=fn::AEqual>
inline bool equals(const t1 &p1,const t2 &p2,tPredicate pComp=tPredicate())
{
    return detail::equals(p1,p2,pComp,QAnd<QFastSizeRange<t1>,QFastSizeRange<t2>>());
}
    
///check if all the elements in two ranges are equal, case-insensitively

///\param p1 the first range
///\param p2 the second range
///\param pComp the function to use to check for element equality
///
///\return `true` if all elements in the two ranges are equal
///
///This function is equivalent to `equals(p1,p2,fn::iequal())`
template<typename t1,typename t2>
inline bool iequals(const t1 &p1,const t2 &p2)
{
    return equals(p1,p2,fn::iequal());
}

///check if the beginning of one range is equal to another range

///\param pInput the input range
///\param pTest the test range
///\param pComp the function to use to check for element equality
///
///\return `true` if the input range starts with the elements in the test range
///
///If it is possible to obtain the size of the range in a fast way (random-access iterator ranges and containers
///with a size() function) then the size will be checked first and std::equal will be used.
template<typename tInput,typename tTest,typename tPredicate=fn::AEqual>
inline bool starts_with(const tInput &pInput,const tTest &pTest,tPredicate pComp=tPredicate())
{
    return detail::starts_with(pInput,pTest,pComp,QAnd<QFastSizeRange<tInput>,QFastSizeRange<tTest>>());
}

///check if the beginning of one range is equal to another range

///\param pInput the input range
///\param pTest the test range
///\param pComp the function to use to check for element equality
///
///\return `true` if the input range starts with the elements in the test range
///
///This function is equivalent to `starts_with(pInput,pTest,fn::iequal())`
template<typename tInput,typename tTest>
inline bool istarts_with(const tInput &pInput,const tTest &pTest)
{
    return starts_with(pInput,pTest,fn::iequal());
}

///check if the end of one range is equal to another range

///\param pInput the input range
///\param pTest the test range
///\param pComp the function to use to check for element equality
///
///\return `true` if the input range ends with the elements in the test range
///
///\todo create a version that works for non-bidirectional iterators and is optimized for random-access
///iterators.
template<typename tInput,typename tTest,typename tPredicate=fn::AEqual>
bool ends_with(const tInput &pInput,const tTest &pTest,tPredicate pComp=tPredicate())
{
    auto lInputI=range_end(pInput);
    auto lTestI=range_end(pTest);

    auto lInputB=range_begin(pInput);
    auto lTestB=range_begin(pTest);

    while(lTestI!=lTestB)
    {
        if(lInputI==lInputB) return false;
        if(!pComp(*(--lInputI),*(--lTestI))) return false;
    }

    return true;
}

///check if the end of one range is equal to another range, case-insensitively

///\param pInput the input range
///\param pTest the test range
///\param pComp the function to use to check for element equality
///
///\return `true` if the input range ends with the elements in the test range
///
///This function is equivalent to `ends_with(pInput,pTest,fn::iequal())`
template<typename tInput,typename tTest>
inline bool iends_with(const tInput &pInput,const tTest &pTest)
{
    return ends_with(pInput,pTest,fn::iequal());
}

///check if one range contains another range

///\param pInput the input range
///\param pTest the test range
///\param pComp the function to use to check for element equality
///
///\return `true` if the input range contains the test range as a subsequence
template<typename tInput,typename tTest,typename tPredicate=fn::AEqual>
inline bool contains(const tInput &pInput,const tTest &pTest,tPredicate pComp=tPredicate())
{
    auto lInput=range(pInput);
    return std::search(lInput.begin(),lInput.end(),range_begin(pTest),range_end(pTest),pComp)!=lInput.end();
}

///check if one range contains another range, case-insensitively

///\param pInput the input range
///\param pTest the test range
///\param pComp the function to use to check for element equality
///
///\return `true` if the input range contains the test range as a subsequence
///
///This function is equivalent to `contains(pInput,pTest,fn::iequal())`
template<typename tInput,typename tTest>
inline bool icontains(const tInput &pInput,const tTest &pTest)
{
    return contains(pInput,pTest,fn::iequal());
}

//@}

///@}

/*namespace buola*/ }

#endif
